//
// Created by spiro on 19-4-8.
//

#include <stdlib.h>
#include "sort.h"

void bubble_sort(int * arr, int len) {
    int i, j;
    int temp;
    for (i = 0; i < (len - 1); ++i) {
        for (j = len - 1; j > i; --j) {
            if (arr[j] < arr[j - 1]) {
                temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

void insertion_sort(int * arr, int len) {
    int i;
    int j;
    int key;
    for (i = 1; i < len; ++i) {
        key = *(arr + i);
        for (j = (i - 1); j >= 0; j--) {
            if (*(arr + j) > key) {
                *(arr + j + 1) = *(arr + j);
            } else {
                break;
            }
        }
        *(arr + j + 1) = key;
    }
}

static void merge(int * arr, int p, int q, int r) {
    int l_len = q - p + 1;
    int r_len = r - q;

    int l_arr[l_len];
    int r_arr[r_len];

    int i, j;

    for (i = 0; i < l_len; ++i) {
        l_arr[i] = arr[p + i];
    }

    for (j = 0; j < r_len; ++j) {
        r_arr[j] = arr[q + j + 1];
    }

    i = j = 0;

    for (int k = p; k < (r + 1); ++k) {

        if (i == l_len) {
            arr[k] = r_arr[j];
            j++;
            continue;
        }

        if (j == r_len) {
            arr[k] = l_arr[i];
            i++;
            continue;
        }

        if (l_arr[i] <= r_arr[j]) {
            arr[k] = l_arr[i];
            i++;
        } else {
            arr[k] = r_arr[j];
            j++;
        }
    }
}

static void _merge_sort(int * arr, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        _merge_sort(arr, p, q);
        _merge_sort(arr, q + 1, r);
        merge(arr, p, q, r);
    }
}

void merge_sort(int * arr, int len) {
    _merge_sort(arr, 0, len - 1);
}

/**
 * Max heapify arr, index i as root.
 * if sub left tree exist, it is heap, if sub right tree exist, it same is heap.
 * @param arr
 * @param len
 * @param i
 */
static void max_heapify(int * arr, int len, int i) {

    int r = (i + 1) << 1;  // right index = 2*(i + 1)
    int l = r - 1;         // left index = 2*(i + 1) - 1

    int largest = i;

    if (l >= len) {
        return;
    }

    if (arr[l] > arr[largest]) {
        largest = l;
    }

    if (r < len && arr[r] > arr[largest]) {
        largest = r;
    }

    if (largest != i) {
        // exchange
        arr[i] = arr[i] ^ arr[largest];
        arr[largest] = arr[largest] ^ arr[i];
        arr[i] = arr[largest] ^ arr[i];

        max_heapify(arr, len, largest);
    }
}

/**
 * Build a max heap from array
 * @param arr
 * @param len
 */
static void build_max_heap(int * arr, int len) {
    int first_nonleaf = (len / 2) - 1;   // floor(len / 2) - 1
    for (int i = first_nonleaf; i >= 0; --i) {
        max_heapify(arr, len, i);
    }
};

void heap_sort(int * arr, int len) {
    build_max_heap(arr, len);
    int temp;
    for (int i = (len - 1); i > 0; --i) {
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        max_heapify(arr, i, 0);
    }
}

/**
 * Partition arr[p..r] to arr[p..q-1] and arr[q+1, r], satisfy below:
 * 1. each element in arr[p..q-1] less than arr[q],
 * 2. each element in arr[q+1..r] greater than arr[q]
 * @param arr
 * @param p
 * @param r
 * @return  q
 */
static int qs_partition(int *arr, int p, int r) {
    int x = arr[r];
    int i = p - 1;
    int temp;
    int q;

    for (int j = p; j < r; ++j) {
        if (arr[j] < x) {
            i++;
            if (i != j) {
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }
    q = i + 1;
    if (r != q) {
        arr[r] = arr[q];
        arr[q] = x;
    }

    return q;
}

static void _quick_sort(int * arr, int p, int r) {
    int q;
    if (p < r) {
        q = qs_partition(arr, p, r);
        _quick_sort(arr, p, q - 1);
        _quick_sort(arr, q + 1, r);
    }
}

void quick_sort(int * arr, int len) {
    _quick_sort(arr, 0, len - 1);
}

static int randomized_qs_partition(int * arr, int p, int r) {
    int len = r - p + 1;
    int i = (rand() % len) + p;
    int temp = arr[i];
    arr[i] = arr[r];
    arr[r] = temp;
    qs_partition(arr, p, r);
}

static void _randomized_quick_sort(int * arr, int p, int r) {
    int q;
    if (p < r) {
        q = randomized_qs_partition(arr, p, r);
        _randomized_quick_sort(arr, p, q - 1);
        _randomized_quick_sort(arr, q + 1, r);
    }
}

void randomized_quick_sort(int * arr, int len) {
    _randomized_quick_sort(arr, 0, len - 1);
}
